class Solution {
public:
    const int mod = 1e9 + 7;
    static const int N = 110;
    int f[N][N];
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        f[0][0] = 1;
        //f[i][j]表示总人数等于i，总利润至少为j的方案数
        for(int i = 1; i <= group.size(); ++i)
        {
            int v = group[i - 1], w = profit[i - 1];
            for(int j = n; j >= v; --j)
                for(int t = minProfit; t >= 0; --t)
                    f[j][t] =(f[j][t] +  f[j - v][max(0, t - w)]) % mod;
            // print(n, minProfit);
        }
        int res = 0;
        for(int i = 0; i <= n; ++i)
            res = (res + f[i][minProfit]) % mod;
        return res;
    }
};